/**
 * @author VernHe
 * @date 2021年07月12日 11:03
 * <p>
 * <p>
 * <p>
 * 338. 比特位计数
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 2
 * 输出: [0,1,1]
 * 示例 2:
 * <p>
 * 输入: 5
 * 输出: [0,1,1,2,1,2]
 * <p>
 * <p>
 * 规律：
 * 对于奇数，其最低位肯定是1，换句话说就是1的个数比前一个偶数多1
 * <p>
 * 对于偶数：
 * 比如 [1] 2  4  8 ... 他们1的个数都是相同的
 * 再比如 [3] 6  12  24 ... 他们1的个数也都是相同的
 * 相同的原因是他们是前一个的2倍，换句话说就是
 * 相当于左移一位，右边补了个0而已，因此对于偶数i,它1的个数和i/2一样
 */
public class Solution_0338 {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) {
                // 如果奇数，就在前一个结果的基础上加1
                result[i] = result[i - 1] + 1;
            } else {
                // 如果是偶数，1的个数就和i/2的结果一样
                result[i] = result[i >> 1];
            }
        }
        return result;
    }
}
